package com.mingqi.hw.test91100;

/** 101 【分积木】
 * Solo和koko是两兄弟，妈妈给了他们一大堆积木，每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配，弟弟koko要求两个人获得的积木总重量“相等”（根据Koko的逻辑），个数可以不同，不然就会哭，但koko只会先将两个数转成二进制再进行加法，而且总会忘记进位（每个进位都忘记）。如当25（11101）加11（1011）时，koko得到的计算结果是18（10010）：
 * 11001
 * +01011--------
 * 10010
 * Solo想要尽可能使自己得到的积木总重量最大，且不让koko哭。
 * 输入描述:
 * 3
 * 3 5 6
 * 第一行是一个整数N(2≤N≤100)，表示有多少块积木；第二行为空格分开的N个整数Ci(1≤Ci≤106)，表示第i块积木的重量。
 * 输出描述:
 * 11
 * 让koko不哭，输出Solo所能获得积木的最大总重量；否则输出“NO”。
 * 示例1
 * 输入
 * 3
 * 3 5 6
 * 输出
 * 11
 * 备注:
 * 如果能让koko不哭，输出Solo所能获得的积木的总重量，否则输出-1。
 * 该样例输出为11。
 * 解释：Solo能获得重量为5和6的两块积木，5转成二级制为101，6转成二进制位110，按照koko的计算方法（忘记进位），结果为11(二进制)。Koko获得重量为3的积木，转成二进制位11(二进制)。Solo和koko得到的积木的重量都是11(二进制)。因此Solo可以获得的积木的总重量是5+6=11（十进制）。
 */
import java.util.Scanner;

public class ZT101 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取积木数量
        int N = scanner.nextInt();

        // 读取积木重量
        int[] weights = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = scanner.nextInt();
        }

        // 调用函数计算结果
        System.out.println(maxWeightForSolo(weights));

        scanner.close();
    }

    // 辅助函数：将整数转换为二进制字符串，不考虑前导零
    private static String toBinaryString(int num) {
        return Integer.toBinaryString(num).replaceFirst("^0+(?!$)", "");
    }

    // 主函数：计算Solo可以获得的积木的最大总重量
    private static String maxWeightForSolo(int[] weights) {
        // 尝试所有可能的子集组合，记录两个集合在Koko的二进制加法下的结果
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }

        int bestWeight = 0; // Solo可以得到的最大重量
        boolean foundSolution = false; // 是否找到解决方案

        // 遍历所有可能的组合
        for (int mask = 1; mask < (1 << weights.length); mask++) {
            int soloWeight = 0;
            int kokoWeight = 0;

            // 计算当前mask下Solo和Koko的重量
            for (int i = 0; i < weights.length; i++) {
                if ((mask & (1 << i)) != 0) {
                    soloWeight += weights[i];
                } else {
                    kokoWeight += weights[i];
                }
            }

            // 转换为二进制字符串，并计算无进位的和
            String soloBinary = toBinaryString(soloWeight);
            String kokoBinary = toBinaryString(kokoWeight);

            // 如果两个二进制字符串长度不同，需要在较短的字符串前补零
            StringBuilder sbSolo = new StringBuilder(soloBinary);
            StringBuilder sbKoko = new StringBuilder(kokoBinary);
            while (sbSolo.length() < sbKoko.length()) {
                sbSolo.insert(0, '0');
            }
            while (sbKoko.length() < sbSolo.length()) {
                sbKoko.insert(0, '0');
            }

            // 计算无进位的和
            int noCarrySum = 0;
            for (int i = 0; i < sbSolo.length(); i++) {
                noCarrySum += sbSolo.charAt(i) - '0' + sbKoko.charAt(i) - '0';
            }

            // 如果无进位的和相等，则更新最大重量
            if (noCarrySum == 0) {
                foundSolution = true;
                bestWeight = Math.max(bestWeight, soloWeight);
            }
        }

        // 如果没有找到解决方案，返回"NO"
        if (!foundSolution) {
            return "NO";
        }

        // 返回Solo可以得到的最大重量
        return String.valueOf(bestWeight);
    }
}

class SoloAndKokoDynamicProgramming {

   public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取积木数量
        int N = scanner.nextInt();

        // 读取积木重量
        int[] weights = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = scanner.nextInt();
        }

        // 调用函数计算结果
        System.out.println(maxWeightForSoloDP(weights));

        scanner.close();
    }

    // 动态规划函数，计算Solo可以获得的积木的最大总重量
    private static String maxWeightForSoloDP(int[] weights) {
        int N = weights.length;
        int totalWeight = 0;
        for (int weight : weights) {
            totalWeight += weight;
        }

        // dp[i][j] 表示前i个积木，能否凑出无进位和为j的二进制数
        boolean[][] dp = new boolean[N + 1][totalWeight * 2 + 1]; // 乘以2是为了处理可能的进位
        dp[0][0] = true; // 初始条件，没有积木时，和为0是可能的

        // 填充dp数组
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= totalWeight * 2; j++) {
                dp[i][j] = dp[i - 1][j]; // 不选择第i个积木
                if (j >= weights[i - 1]) {
                    // 尝试加上第i个积木（注意这里要处理可能的进位）
                    int binarySum = j - weights[i - 1] + (getBinaryLastDigit(weights[i - 1]) + getBinaryLastDigit(j - weights[i - 1])) % 2;
                    dp[i][j] = dp[i][j] || dp[i - 1][binarySum];
                }
            }
        }

        // 从最大的可能和开始检查，看是否能凑出和为totalWeight（无进位）的两组积木
        for (int j = totalWeight * 2; j >= 0; j--) {
            if (dp[N][j] && j - getBinaryLastDigit(j) == totalWeight) {
                // 如果找到了，则j - getBinaryLastDigit(j)是Solo的重量（因为Koko会忘记进位）
                return String.valueOf(j - getBinaryLastDigit(j));
            }
        }

        // 如果没有找到解决方案，返回"NO"
        return "NO";
    }

    // 辅助函数：获取整数的二进制表示的最后一位数字（0或1）
    private static int getBinaryLastDigit(int num) {
        return num & 1;
    }
}